Background: Many probiotic bacteria have been described as promising tools for the treatment and prevention of inflammatory bowel diseases (IBDs). Most of these bacteria are lactic acid bacteria, which are part of the healthy human microbiota. However, little is known about the effects of transient bacteria present in normal diets, including Lactococcus lactis. Methods: In the present study, we analysed the immunomodulatory effects of three L. lactis strains in vitro using intestinal epithelial cells. L. lactis NCDO 2118 was administered for 4 days to C57BL/6 mice during the remission period of colitis induced by dextran sodium sulphate (DSS). Results: Only one strain, L. lactis NCDO 2118, was able to reduce IL-1β-induced IL-8 secretion in Caco-2 cells, suggesting a potential anti-inflammatory effect. Oral treatment using L. lactis NCDO 2118 resulted in a milder form of recurrent colitis than that observed in control diseased mice. This protective effect was not attributable to changes in secretory IgA (sIgA); however, NCDO 2118 administration was associated with an early increase in IL-6 production and sustained IL-10 production in colonic tissue. Mice fed L. lactis NCDO 2118 had an increased number of regulatory CD4+ T cells (Tregs) bearing surface TGF-β in its latent form (Latency-associated peptide-LAP) in the mesenteric lymph nodes and spleen. Conclusions: Here, we identified a new probiotic strain with a potential role in the treatment of IBD, and we elucidated some of the mechanisms underlying its anti-inflammatory effect.